package T31_T40;

import java.util.HashMap;
import java.util.Map;

//LRU缓存
public class T35 {
    private static class Node{
        int key,value;
        Node prev,next;
        Node (int key,int value){
            this.key=key;
            this.value=value;
        }
    }
    private final int capacity;
    //定义哨兵结点dummy指向链表的头部
    private final Node dummy=new Node(0,0);
    private final Map<Integer,Node> keyToNode=new HashMap<>();
    //思路：1使用双向链表保存缓存的值，以node结点形式存储
    //2 使用hashmap存储node，以node.value作为key
    //3 每次put和get，将对应结点移到链表头结点

    public T35(int capacity) {
        this.capacity=capacity;
        dummy.next=dummy;
        dummy.prev=dummy;
    }

    public int get(int key) {
        Node node = getNode(key);//该操作会将获取到的结点移到链表头部（dummy之后）
        return node!=null? node.value:-1;
    }

    public void put(int key, int value) {
        //如果哈希表中已经有这个key了,就重新赋值，且将对应结点移到头部
        Node node = getNode(key);
        if (node!=null){
            node.value=value;
            return;
        }
        //如果没有就存入哈希表中，如果超出容量就删除最后一个结点
        node=new Node(key, value);
        keyToNode.put(key,node);
        pushFront(node);
        if (keyToNode.size()>capacity){
            Node backNode = dummy.prev;
            keyToNode.remove(backNode.key);
            remove(backNode);
        }


    }
    //根据key获取node结点，并且将该节点移到链表首部
    private Node getNode(int key){
        Node node = keyToNode.get(key);
        if (node==null)return null;
        remove(node);//删除结点
        pushFront(node);//移到头结点
        return node;
    }
    //将该结点删除
    private void remove(Node n){
        n.prev.next=n.next;
        n.next.prev=n.prev;
    }
    //将结点移到链表的头结点
    private void pushFront(Node n){
        n.next=dummy.next;
        n.prev=dummy;
        n.next.prev=n;
        n.prev.next=n;
    }

}
